"""谢尔宾斯基(Sierpinski)三角形控制台输出"""

def sierpinski(size, length, char='·', back=' '):
    """
    构造谢尔宾斯基三角形数组

    @param size   : 阶数
    @param length : 最小三角形边长
    @param char   : 填充符号
    @param back   : 背景符号
    """

    # 图形数组
    nrows = length * 2 ** (size - 1)
    ncols = length * 2 ** size - 1
    fig = [[back for j in range(ncols)] for i in range(nrows)]

    def draw(row, col, lev):
        """
        @param row : 起点横坐标
        @param col : 起点纵坐标
        @param lev : 当前层级
        """

        # 基本情形 -- 单个最小三角形
        if lev == 1:
            for i in range(length):
                if i != length - 1:
                    fig[row + i][col - i] = fig[row + i][col + i] = char
                else:
                    for j in range(col - i, col + i + 1, 2):
                        fig[row + i][j] = char
        # 层级 > 1，找到另外两个同层级出发点
        else:
            next_left = (row + length * 2 ** (lev - 2),
                         col - length * 2 ** (lev - 2))
            next_right = (row + length * 2 ** (lev - 2),
                          col + length * 2 ** (lev - 2))
            draw(row, col, lev - 1)
            draw(*next_left, lev - 1)
            draw(*next_right, lev - 1)

    # 非法输入
    if size < 0:
        return fig

    # 一般递归情形
    draw(0, ncols // 2, size)

    return fig


def print_array(array):
    print('\n'.join([''.join(line) for line in array]))


if __name__ == "__main__":
    arr = sierpinski(4, 3, '*', '·')
    print_array(arr)
